//n进制转m进制
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll calc(char i)
{
	if(i >= 'A') return 10 + (i-'A');
	else return i - '0';
}
int main()
{
	ll t = 0;
	cin >> t;
	while(t--)
	{
		int n,m;
		string num;
		cin >> n >> m >> num;
		//转10进制
		ll ans = 0;
		for(int i = 0; i < num.size(); i++)
		{ 
			ans = ans * n + calc(num[i]) ;
		}
		//转m进制
		if(ans == 0) 
		{
			cout << '0' << '\n';
			continue;
		}
		string result ="";
		while(ans != 0)
		{
			int t = ans % m;
			if(t <= 9) result += (char)(t + '0');
			else result += (char)(t - 10 + 'A');
			ans /= m;
		}
		reverse(result.begin(),result.end());
		cout << result <<'\n';
	}  
	return 0;
}
